#ifndef OPTFRAME_PATTERNIMPROVEMENT_HPP_
#define OPTFRAME_PATTERNIMPROVEMENT_HPP_

#include "../../OptFrame/Heuristic.hpp"
#include "../../OptFrame/Evaluator.hpp"

/*struct bestPos
 {
 int periodo;
 int rota;
 int posicao;
 };*/

class PatternImprovement: public Heuristic<RepPRVP, MemPRVP>
{
private:
	PRVPEvaluator& eval;
	PRVPProblemInstance& pPRVP;
	double static const inf = 9999999;

	vector<int> decompoeEscolha(int escolha)
	{
		vector<int> periodos;
		int p = pPRVP.nPeriod - 1;
		while (escolha != 0)
		{
			if (escolha % 2 == 1)
			{
				periodos.push_back(p);
			}
			escolha = escolha / 2;
			p--; //passando para o proximo periodo
		}

		return periodos;
	}

	double removeCliInRoute(int id, vector<vector<int> >& rt, vector<double> & cap)
	{
		double custo = 0;//custo da remoção do cliente
		for (unsigned int r = 0; r < rt.size(); r++)
			for (unsigned int c = 0; c < rt.at(r).size(); c++)
			{
				if (id == rt.at(r).at(c))
				{
					if (rt.at(r).size() == 1)//se tiver somente um elemento
					{
						custo = -(*pPRVP.dist)(0, rt.at(r).at(c)) - (*pPRVP.dist)(rt.at(r).at(c), 0);
						cap.at(r) -= pPRVP.dados->at(id).at(DEMANDA);
						return custo;
					}
					else
					{
						//retornando o custo da remoção desse cliente
						if (c == 0)
						{
							custo = (*pPRVP.dist)(0, rt.at(r).at(c + 1)) - (*pPRVP.dist)(0, rt.at(r).at(c)) - (*pPRVP.dist)(rt.at(r).at(c), rt.at(r).at(c + 1));
						}
						else if (c == rt.at(r).size() - 1)
						{
							custo = (*pPRVP.dist)(rt.at(r).at(c - 1), 0) - (*pPRVP.dist)(rt.at(r).at(c - 1), rt.at(r).at(c)) - (*pPRVP.dist)(rt.at(r).at(c), 0);
						}
						else
						{
							custo = (*pPRVP.dist)(rt.at(r).at(c - 1), rt.at(r).at(c + 1)) - (*pPRVP.dist)(rt.at(r).at(c - 1), rt.at(r).at(c)) - (*pPRVP.dist)(rt.at(r).at(c), rt.at(r).at(c + 1));
						}
					}
					rt.at(r).erase(rt.at(r).begin() + c);
					//atualizando a capacidade dessa rota
					cap.at(r) -= pPRVP.dados->at(id).at(DEMANDA);
					return custo;
				}
			}

		return custo;
	}

	double removeCli(RepPRVP& rep, int c, ADS& ads, vector<vector<double> >& cap)
	{
		double custo = 0;
		for (int i = 0; i < ads.getLocal_cli().at(c).size(); i++)
		{
			custo += removeCliInRoute(c, rep.at(ads.getLocal_cli().at(c).at(i)), cap.at(ads.getLocal_cli().at(c).at(i)));
		}

		return custo;

	}

	double bestInsertion(vector<vector<int> > routes, int periodo, int cli, bestPos & pos, vector<double>& cap)
	{
		//melhor valor de inserção
		double best_insert = inf;
		//melhor posicao de inserção
		pos.periodo = periodo;

		double aux_insert;

		//pegando a matriz de distancia
		Matrix<double>& dist = (*pPRVP.dist);

		/*cout<<dist<<endl;
		 exit(1);*/

		//verificando a melhor posição em todos os periodos
		for (int r = 0; r < routes.size(); r++)
		{
			if (routes.at(r).size() == 0)// se a rota estiver vazia

			{
				aux_insert = dist(0, cli) + dist(cli, 0);

				if (aux_insert < best_insert)
				{
					best_insert = aux_insert;
					pos.rota = r;
					pos.posicao = 0;
				}

			}
			else //caso a rota não estiver vazia

			{
				//verificando se ao adicionar o cliente a essa rota não estoura a capacidade do veículo
				if (cap.at(r) + pPRVP.dados->at(cli).at(DEMANDA) <= (pPRVP.capacidade * 1.2))
				{
					//testando se a melhor posição fica entre o depósito e o primeiro cliente da rota "r"
					aux_insert = dist(0, cli) + dist(cli, routes.at(r).at(0)) - dist(0, routes.at(r).at(0));

					if (aux_insert < best_insert)
					{
						best_insert = aux_insert;
						pos.rota = r;
						pos.posicao = 0;
					}

					//testando para as demais posições
					for (int c = 0; c < routes.at(r).size() - 1; c++)
					{
						aux_insert = dist(routes.at(r).at(c), cli) + dist(cli, routes.at(r).at(c + 1)) - dist(routes.at(r).at(c), routes.at(r).at(c + 1));
						if (aux_insert < best_insert)
						{
							best_insert = aux_insert;
							pos.rota = r;
							pos.posicao = c + 1;
						}
					}
					//testando se a melhor posição fica entre o ultimo cliente da rota "r" e o depósito
					aux_insert = dist(routes.at(r).at(routes.at(r).size() - 1), cli) + dist(cli, 0) - dist(routes.at(r).at(routes.at(r).size() - 1), 0);
					if (aux_insert < best_insert)
					{
						best_insert = aux_insert;
						pos.rota = r;
						pos.posicao = routes.at(r).size();
					}
				}
			}
		}

		return best_insert;
	}

public:

	using Heuristic<RepPRVP, MemPRVP>::exec; // prevents name hiding

	PatternImprovement(PRVPEvaluator& _eval, PRVPProblemInstance& _pPRVP) :
		eval(_eval), pPRVP(_pPRVP)
	{
	}

	virtual ~PatternImprovement()
	{
	}

	virtual void exec(Solution<RepPRVP>& s, double timelimit, double target_f)
	{
		Evaluation<MemPRVP>& e = eval.evaluate(s.getR());

		exec(s, e, timelimit, target_f);

		delete &e;
	}

	virtual void exec(Solution<RepPRVP>& s, Evaluation<MemPRVP>& e, double timelimit, double target_f)
	{
		//vetores para armazenar o valor da melhor inserção, e a posição da melhor inserção.
		vector<double> evals(pPRVP.nCli + 1, 0);
		vector < vector<bestPos> > pos(pPRVP.nCli + 1);

		//calculando quando da capacidade do veículo está sendo utilizada
		vector < vector<double> > cap_utilizada;

		for (int p = 0; p < s.getR().size(); p++)
		{
			vector<double> aux;
			for (int r = 0; r < s.getR().at(p).size(); r++)
			{
				double cap = 0;
				for (int c = 0; c < s.getR().at(p).at(r).size(); c++)
				{
					cap += pPRVP.dados->at(s.getR().at(p).at(r).at(c)).at(DEMANDA);
				}
				aux.push_back(cap);
			}
			cap_utilizada.push_back(aux);
		}

		for (int c = 1; c < evals.size(); c++) //para cada cliente excluindo o depósito

		{
			RepPRVP rep = s.getR(); //fazendo uma cópia da representação para manter a solução passada como parametro

			//fazendo uma cópia da capacidade utilizada até então
			vector < vector<double> > cap_util_atual = cap_utilizada;
			double custoRemocao = removeCli(rep, c, e.getM(), cap_util_atual); // removendo o cliente "c" da solução

			//estruturas auxiliares para cada combinação de periodos de cada cliente
			double eval_escolha = 0;
			vector<bestPos> pos_aux;

			double bestEval = inf;
			vector<bestPos> bestPosCli;

			//para cada uma das combinações
			for (int escolha = 0; escolha < pPRVP.dados->at(c).at(NCOMB); escolha++)
			{
				eval_escolha = custoRemocao;
				pos_aux.clear();

				//decompondo a primeir escolha
				vector<int> periodos = decompoeEscolha(pPRVP.dados->at(c).at(NCOMB + escolha + 1));
				//para cada periodo decomposto
				//	fazer as inserções por periodo guardando os menores valores
				for (int p = 0; p < periodos.size(); ++p)
				{
					bestPos aux;
					eval_escolha += bestInsertion(rep.at(periodos.at(p)), periodos.at(p), c, aux, cap_util_atual.at(periodos.at(p)));
					pos_aux.push_back(aux);
				}

				if (eval_escolha < bestEval)
				{
					bestEval = eval_escolha;
					bestPosCli = pos_aux;
				}
			}

			//após analisar todas as escolhas, ver qual foi a melhor escolha para esse cliente e adiciona-la as avaliações gerais
			evals.at(c) = bestEval;
			pos.at(c) = bestPosCli;

		}

		//escolhendo a melhor inserção entre todas e realizando essa inserção

		//escolhendo a melhor inserção entre todas
		double bestEval = inf;
		int bestCli;

		for (int c = 1; c < evals.size(); c++)
		{
			if (evals.at(c) < bestEval)
			{
				bestEval = evals.at(c);
				bestCli = c;
			}
		}
		/*cout << evals << endl;
		 cout << "bestEval: " << bestEval << endl;
		 cout << "BestCli: " << bestCli << endl;

		 //exit(1);*/

		//removendo o melhor cliente da posição atual dele na solução corrente
		removeCli(s.getR(), bestCli, e.getM(), cap_utilizada);

		//marcando os periodos que foram removidos
		for (int i = 0; i < e.getM().getLocal_cli().at(bestCli).size(); ++i)
		{
			e.getM().getStatus().at(e.getM().getLocal_cli().at(bestCli).at(i)) = true;
		}

		//atualizando a ADS para o cliente selecionado
		e.getM().getLocal_cli().at(bestCli).clear();
		//inserindo o cliente na melhor posição em cada período
		for (int i = 0; i < pos.at(bestCli).size(); i++)
		{
			int periodo = pos.at(bestCli).at(i).periodo; //periodo
			int rota = pos.at(bestCli).at(i).rota; // rota
			int posicao = pos.at(bestCli).at(i).posicao; // posição de inserção

			e.getM().getStatus().at(periodo) = true;

			//fazendo a inserção
			s.getR().at(periodo).at(rota).insert(s.getR().at(periodo).at(rota).begin() + posicao, bestCli);

			//atualizando a memória com as novas posições do cliente
			e.getM().getLocal_cli().at(bestCli).push_back(periodo);
		}

		eval.evaluate(e, s.getR()); // updates 'e'
	}

};

#endif /*OPTFRAME_PATTERNIMPROVEMENT_HPP_*/
